package com.lry.basic.algorithm.greedy;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.TreeSet;

public class IPO {
    public static void main(String[] args) {
        int[] profits = new int[10000];
        for(int i=0;i<10000;i++){
            profits[i] = 10000;
        }

        Random random = new Random();
        int[] cap = new int[10000];
        for(int i=0;i<10000;i++){
            cap[i] = random.nextInt(5000);
        }



//        System.out.println(findMaximizedCapital2(10000, 10000, profits, cap));

        //输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
        System.out.println(findMaximizedCapital2(2, 10, new int[]{1,2,3}, new int[]{0,1,1}));
    }

    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int res = w;

        TreeSet<Integer> set = new TreeSet();

        while(set.size()<k){
            int max = -1;
            int maxI = -1;

            for(int i=0;i<capital.length;i++){
                if(res>=capital[i]&&!set.contains(i)){
                    if(profits[i]>max){
                        max = profits[i];
                        maxI = i;
                    }
                }
            }

            if(max!=-1&&maxI!=-1){
                res+=max;
                set.add(maxI);
            }else{break;}
        }

        return res;
    }

    //输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
    public static int findMaximizedCapital2(int k, int w, int[] profits, int[] capital) {

        int[][] arr = new int[profits.length][2];
        for(int i=0;i<profits.length;i++){
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }
        //对初始启动资金进行从小到大排序
        Arrays.sort(arr,(a,b)->a[0]-b[0]);

        //构建收益的最大堆
        PriorityQueue<Integer> queue = new PriorityQueue<>((x,y)->y-x);

        int cur = 0;
        for(int i=0;i<k;i++){
            while(cur<profits.length && arr[cur][0]<=w ){
                queue.add(arr[cur][1]);
                cur++;
            }

            if(queue.isEmpty()){
                break;
            }
            w+= queue.poll();
        }

        return w;
    }
}
